package hot100.logos81To90;

/**
 * @author logos
 * date 2025/7/18 18:49
 * @version v1.0
 * @Package hot100.logos81To90
 */
public class logos87 {


    /**
     * 87. 最长递增子序列
     * https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-100-liked
     */
    class Solution {
        public int lengthOfLIS(int[] nums) {
            int n = nums.length;
            int ans = 0;
            int[] dp = new int[n];
            for (int i = 0; i < n; i++) {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = Math.max(dp[i], 1 + dp[j]);
                    }
                }
                ans = Math.max(ans, dp[i]);
            }
            return ans;
        }
    }
}
